<?php

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
error_reporting(E_ALL);
$time = microtime(true);

/**
 * Description of arithmetic
 *
 * @author Administrator
 */
class Arithmetic {

    const PHP_TAB = "\t";

    /**
     * king 猴子选国王算法
     * 函数的含义说明
     *
     * @access public
     * @param int $n 猴子总数
     * @param int $m 约定的数
     * @return int
     */
    public static function King($n, $m) {
        $monkeys = range(1, $n);

        $i = 1;

        //当$m>$n时 取余 减少循环次数
        if ($m > $n) {
            $temp = $m % count($monkeys); //
        } else {

            $temp = $m;
        }

        while (count($monkeys) > 1) {

//当$temp == 0 时 次数是 count($monkeys)
            if ($temp == 0) {
                $temp = count($monkeys);
            }
            foreach ($monkeys as $key => $val) {
                if (($i ) % $temp == 0) { //当($i )被$temp整除 即数到$m 时 删除当前项 重新计数
                    $i = 1;
                    unset($monkeys[$key]);
                    $num = count($monkeys);
                    if ($num <= 1) {
// 当符合条件时 返回 国王数据
                        return array_pop($monkeys);
                    }
                    $temp = $m % $num;
                    if ($temp == 0) {
                        $temp = $num;
                    }
                    continue;
                } else {
                    $i++;
                }
            }
        }
// 当符合条件时 返回 国王数据
        return array_pop($monkeys);
    }

    /**
     * Fibonacci 斐波那契算法
     * 函数的含义说明
     *
     * @access public
     * @param int $n 输入的数据
     * @param int $strat 返回的
     * @param int $end 输入的数据
     * @return int
     */
    public static function Fibonacci($n, $strat = 1) {

        if ($n < 1) {

            return 0;
        }
        if ($n < 2) {

            return $strat;
        } else {

            return self::Fibonacci($n - 1) + self::Fibonacci($n - 2);
        }
    }

    /*
     * youhua
     */

    public static function Fibonacci_yh($n, &$Fibonacci = []) {
        if ($n < 1) {
            return 0;
        }


        switch ($n) {
            case 1:

                return 1;
            case 2:

                return 1;
            case 3:

                return 2;

            default :
                if (isset($Fibonacci[$n])) {
                    return $Fibonacci[$n];
                } elseif ($n % 2 == 0) {
                    $big1 = bcmul(self::Fibonacci_yh($n / 2 + 1, $Fibonacci), self::Fibonacci_yh($n / 2, $Fibonacci));

                    $big2 = bcmul(self::Fibonacci_yh($n / 2, $Fibonacci), self::Fibonacci_yh($n / 2 - 1, $Fibonacci));
                    $Fibonacci[$n] = bcadd($big1, $big2);
                    self::addLog($n . self::PHP_TAB . $Fibonacci[$n]);
                    return $Fibonacci[$n];
                } elseif ($n % 2 == 1) {
                    $big1 = bcmul(self::Fibonacci_yh($n / 2 + 3 / 2, $Fibonacci), self::Fibonacci_yh($n / 2 - 1 / 2, $Fibonacci));

                    $big2 = bcmul(self::Fibonacci_yh($n / 2 + 1 / 2, $Fibonacci), self::Fibonacci_yh($n / 2 - 3 / 2, $Fibonacci));
                    $Fibonacci[$n] = bcadd($big1, $big2);

                    self::addLog($n . self::PHP_TAB . $Fibonacci[$n]);

                    return $Fibonacci[$n];
                }
        }
    }

    /**

     * 判断完全数

     *

     * @param num

     * @return

     */
    public static function isWanshu($num) {
        $flag = false;
        $yzh = 0; // 各因子之和
// 循环计算所有因子之和

        for ($i = 1; $i <= $num / 2; $i++) {
            if ($num % $i == 0) {
                $yzh += $i;
            }
        }

// 判断所有因子之和是否和该数本身相等,相等则为完数

        if ($yzh == $num) {
            $flag = true;
        }

        return $flag;
    }

    public static function jitu() {
        for ($ji = 0; $ji <= 35; $ji++) {
            $tu = 35 - $ji;
            if ((2 * $ji + 4 * $tu) == 94) {
                echo '鸡=' . $ji . '\t' . '兔=' . $tu;
            }
        }
    }

    /**

     * 舍罕王赏麦子 Created by titi on 2017/4/17.

     */
    public static function maizi() {
// 麦子数量

        $sum = 0;
        $temp = 1;
// 国际象棋棋盘共64个格

        for ($i = 1; $i <= 64; $i++) {
// 等比数列

            $temp *= 2;
            $sum = $sum + $temp;
        }
        echo '赏赐的麦子数量:', $sum, '粒';
// 假设25000粒麦子为1公斤

        $weight = $sum / 25000 / 1000;
        echo '约合:', $weight, '吨';
    }

    /**

     * 木马板凳 Created by titi on 2017/4/18.

     */
    public static function mmbd() {
        for ($muma = 1; $muma <= 33; $muma++) {
            $bandeng = 33 - $muma;
// 木马三只脚,板凳4只脚

            if ((3 * $muma + 4 * $bandeng) == 100) {
                echo "木马=" + $muma . "\t" . "板凳=" . $bandeng;
            }
        }
    }

    /**
     * Binsch 二分查找
     * 函数的含义说明
     *
     * @access public
     * @param array $array 输入的数组
     * @param int $low 低的部分
     * @param int $high 高的部分
     * @param int $k 需要查找的数
     * @return int
     */
    public static function Binsch($array, $low = 0, $high = 0, $k = 0) {


        if ($low <= $high) {
            $mid = intval(($low + $high) / 2);
            if ($array[$mid] == $k) {
                return $mid;
            } elseif ($k < $array[$mid]) {
                return self::bin_sch($array, $low, $mid - 1, $k);
            } else {
                return self::bin_sch($array, $mid + 1, $high, $k);
            }
        }
        return -1;
    }

    /**
     * Binsch 顺序查找
     * 函数的含义说明      *
     * @access public
     * @param array $array 被查找的数组

     * @param int $k 需要查找的数
     * @return int
     */
    public static function Seqch($array, $k) {

        for ($i = 0, $num = count($array); $i < $num; $i++) {
            if ($array[$i] == $k) {//判断是否是查找的值 查找$k的键值
                return $i;
            }
        }

        return -1;
    }

    /**
     * DeleteArrayElement 线性表的删除
     * 函数的含义说明      *
     * @access public
     * @param array $array 被查找的数组
     * @param int $i 被删除的个数

     * @return array
     */
    public static function DeleteArrayElement($array, $i) {
        $len = count($array);
        for ($j = $i; $j < $len; $j ++) {
            $array[$j] = $array [$j + 1];
        }
        array_pop($array);
        return $array;
    }

    /**
     * BubbleSort 冒泡排序
     * 函数的含义说明      *
     * @access public
     * @param array $array 被排序的数组


     * @return array
     */
    public static function BubbleSort($array) {
        $count = count($array); //计算数组个数
        if ($count <= 0) {//当数组不存在时返回 false
            return false;
        }
        for ($i = 0; $i < $count; $i ++) {
            for ($j = $count - 1; $j > $i; $j--) {
                if ($array[$j] < $array [$j - 1]) {//数组交换
                    $tmp = $array[$j];
                    $array[$j] = $array[$j - 1];
                    $array [$j - 1] = $tmp;
                }
            }
        }
        return $array;
    }

    /**
     * QuickSort 快速排序
     * 快速排序
     * C.R.A.Hoare于1962年提出的一种划分交换排序。
     * 它采用了一种分而治之的策略，
     * 通常称其为分治法(Divide-and-ConquerMethod)。
     * 基本思想：
     * 将原问题分解为若干个规模更小但结构与原问题相似的子问题。
     * 递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
     */
    public static function QuickSort(&$list, $left = 0, $right = null) {
        if (is_null($right)) {
            $right = count($list) - 1;
        }
        $middle = intval(($left + $right) / 2);
        $pivot = $list[$middle];
        $i = $left;
        $j = $right;
//partition
        while ($i <= $j) {
            while ($list[$i] < $pivot) {
                $i++;
            }
            while ($list[$j] > $pivot) {
                $j--;
            }
            if ($i <= $j) {
                $temp = $list[$i];
                $list[$i] = $list[$j];
                $list[$j] = $temp;
                $i++;
                $j--;
            }
        }
//recusion
        if ($left < $j) {
            self::QuickSort($list, $left, $j);
        }
        if ($i < $right) {
            self::QuickSort($list, $i, $right);
        }
    }

    /**
     * InsertSort 插入排序
     * 函数的含义说明      *
     * @access public
     * @param array $array 被排序的数组


     * @return array
     */
    public static function InsertSort($array) {
        $len = count($array);        // 数组个数
        for ($i = 1; $i < $len; $i++) {
            $tmp = $array[$i];
//内层循环控制，比较并插入
            for ($j = $i - 1; $j >= 0; $j--) {
                if ($tmp < $array[$j]) {
//发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
                    $array[$j + 1] = $array[$j];
                    $array[$j] = $tmp;
                } else {
//如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了。
                    break;
                }
            }
        }
        return $array;
    }

    /*
     * 直接插入排序
     */

    public static function StraightInsertSort(array &$arr) {
        $count = count($arr);
//数组中第一个元素作为一个已经存在的有序表
        for ($i = 1; $i < $count; $i ++) {
            $temp = $arr[$i];      //设置哨兵
            for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j --) {
                $arr[$j + 1] = $arr[$j];       //记录后移
            }
            $arr[$j + 1] = $temp;      //插入到正确的位置
        }
    }

    /**
     * MergeSort 归并排序
     * 函数的含义说明      *
     * @access public
     * @param array $a 被排序的数组
     * @param array $b 被排序的数组

     * @return array
     */
    public static function MergeSort($a, $b) {
        $a_i = $b_i = 0;
        $count_a = count($a);
        $count_b = count($b);
        $ret = []; //临时数组;存放排序后的数组
        while ($a_i < $count_a && $b_i < $count_b) {
            if ($a[$a_i] > $b[$b_i]) {
                array_push($ret, $b[$b_i]); //向$ret中插入数据
                $b_i++;
            } else {
                array_push($ret, $a[$a_i]); //向$ret中插入数据
                $a_i++;
            }
        }
        if ($a_i < $count_a) {
            $ret = self::MergeSort($ret, array_slice($a, $a_i)); //从数组中取出未排序的数组;
        }
        if ($b_i < $count_b) {
            $ret = self::MergeSort($ret, array_slice($b, $b_i)); //从数组中取出未排序的数组;
        }
        return $ret;
    }

    /**
     * 堆排序
     * 基本思想:
     * 堆排序(HeapSort)是一树形选择排序。
     * 在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，
     * 利用完全二叉树中双亲结点和孩子结点之间的内在关系，
     * 在当前无序区中选择关键字最大(或最小)的记录。
     * 　
     * 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
     * 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。
     */
    public static function heapSort(array $list) {
        $length = count($list);
        $this->buildHeap($list, $length - 1);
        while (--$length) {
            $temp = $list[0];
            $list[0] = $list[$length];
            $list[$length] = $temp;
            self::heapAdjust($list, 0, $length);
        }
        return $list;
    }

    public static function buildHeap(array &$list, $num) {
        for ($i = floor(($num - 1) / 2); $i >= 0; $i--) {
            self::heapAdjust($list, $i, $num + 1);
        }
    }

    public static function addLog($log) {

        $filehandle = fopen(dirname(__FILE__) . DIRECTORY_SEPARATOR . 'Fibonacci.txt', "a+");

        $str = $log . PHP_EOL;
//写日志
        if (!fwrite($filehandle, $str)) { //写日志失败
            die('写入日志失败');
        }
    }

    public static function heapAdjust(array &$list, $i, $num) {
        if ($i > $num / 2) {
            return;
        }
        $key = $i;
        $leftChild = $i * 2 + 1;
        $rightChild = $i * 2 + 2;
        if ($leftChild < $num && $list[$leftChild] > $list[$key]) {
            $key = $leftChild;
        }
        if ($rightChild < $num && $list[$rightChild] > $list[$key]) {
            $key = $rightChild;
        }
        if ($key != $i) {
            $val = $list[$i];
            $list[$i] = $list[$key];
            $list[$key] = $val;
            self::heapAdjust($list, $key, $num);
// heapPrint($list);
        }
    }

}

$Fibonacci = [];

$i = Arithmetic::Fibonacci_yh(1000000, $Fibonacci);

echo microtime(true) - $time;
//
////多字段排序
//
//$a = [
//    ["id" => 10, "date" => "2017-08-09"],
//    ["id" => 10, "date" => "2017-08-06"],
//    ["id" => 10, "date" => "2017-08-05"],
//    ["id" => 10, "date" => "2017-08-07"],
//    ["id" => 10, "date" => "2017-08-03"],
//    ["id" => 9, "date" => "2017-08-02"],
//    ["id" => 9, "date" => "2017-08-03"],
//    ["id" => 9, "date" => "2017-08-01"],
//    ["id" => 5, "date" => "2017-08-02"],
//    ["id" => 5, "date" => "2017-08-03"],
//    ["id" => 5, "date" => "2017-08-01"],
//    ["id" => 8, "date" => "2017-08-02"],
//    ["id" => 8, "date" => "2017-08-03"],
//    ["id" => 8, "date" => "2017-08-01"],
//];
//
//$ags = [
//    "id" => "asc",
//    "date" => "desc",
//];
//echo '<pre>';
//
//function Fildesort($a, $ags) {
//    $sorts = [];
//
//    foreach ($ags as $filed => $sort) {
//        $data = [];
//        foreach ($a as $key => $item) {
//            $data[$key] = $item[$filed];
//        }
//        $sorts[] = $data;
//        switch ($sort) {
//            case "asc":
//                $sorts[] = SORT_ASC;
//                break;
//            case "desc":
//                $sorts[] = SORT_DESC;
//                break;
//        }
//    }
//    $sorts[] = &$a;
//
//// array_multisort($sorts, $sorts);
//    call_user_func_array('array_multisort', $sorts);
//    return array_pop($sorts);
//}
